Relational databases generally require that every record be uniquely identified by one or a combination of columns. The column that uniquely identifies records is declared to be the primary key (PK) of the table.
A B+ tree data structure is often used to manage database records. In an example implementation, nodes that are leaves of the B+ tree are data pages of database records, and nodes that are parents of the leaves are index pages. The index pages contain primary key values for referencing records in the data pages. The leaves are also sequentially linked to provide sequential access to database records.
Multi-user database applications follow the transaction processing paradigm, which requires processing of transactions comply with the properties denoted as “ACID” (Atomicity, Consistency, Isolation, and Durability) as understood by those skilled in the art. Each transaction issued by the application specifies an operation on the database, and in processing that operation, the database management system (DBMS) adheres to the ACID properties. For consistency and durability, certain pages may be locked while updates are being made so that the state of data is consistent between transactions, and the updates or a specification of operations performed are retentively stored to provide recoverability in the event of a system crash.
Deleting records from the database may result in the database management system (DBMS) merging one or more pages. Merging a page generally involves removal of the page from the B+ tree and returning the page to a free list for subsequent use. In the B+ tree the index page and sequentially previous data page that references the removed page are updated to reflect that the page is no longer in the B+ tree. The user application may issue transactions that delete records, and the DBMS deletes pages from the B+ tree as may be necessary.
One approach to merging a page involves doing so during the course of processing a transaction. That is, in processing a delete transaction the DBMS detects the need to merge a page. The record is first deleted, the DBMS performs the merge of the page, and after the merge is complete, the transaction is committed.
While merging a page in a multi-user database the DBMS must lock the appropriate pages in order to preserve consistency of the data and supporting data structures. However, the locking of the pages during the merging of a page may delay the processing of other transactions. Other transactions seeking access to records stored in, or referenced by, the locked pages must wait to be processed until the transaction that resulted in the merging of the page merge commits its updates and the pages are unlocked. The wait time for the other transactions may range from a fraction of a second to minutes, depending on how quickly the transaction with the delete operation commits its updates. In some applications, the commit of the transaction may require manual user intervention, resulting in the delay being dependent on user attentiveness.
In another approach to merging pages, a DBMS may require a database administrator to periodically run a utility to merge pages. However, this requires additional time for managing the database.
A method and system that address these and other related issues are therefore desirable.